package tree;

/**
 * @Description 剑指 Offer 68 - II. 二叉树的最近公共祖先
 * @Author Firenut
 * @Date 2023-02-02 01:27
 */
public class T68_II_lowestCommonAncestor {

    // 递归的思路是从最下层然后往上层回溯的 所以一定是根结点先遍历，至于先左还是先右都可以
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) { //递归终止条件
            return root;
        }
        // 递归左子树
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 递归右子树
        TreeNode right = lowestCommonAncestor(root.right, p, q);


        // 如果左右子树都没有找到，则返回null
        if (left == null && right == null) {
            return null;
        }

        // 如果左子树为null,右子树不为null,返回右子树结果(返回给上层继续查找)
        if (left == null) {
            return right;
        }

        // 如果右子树为null,左子树不为null,返回左子树结果(返回给上层继续查找)
        if (right == null) {
            return left;
        }

        //如果左、右子树都找到了，表示p,q在root的两侧，直接返回root
        return root;
    }
}